
class Solution
{
    /**
     * 问题：获取二进制位，1的个数
     * 链接：https://leetcode.cn/problems/number-of-1-bits/
     */
    //获取1的个数：将数从0 - 31 右移 & 1
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0;i < 32;i++){
            count += (n >> i) & 1;
        }
        return count;
    }

    /**
     * 返回0 - n 中个元素1的比特位个数的数组
     * @param n
     * return bit位为1的个数
     */
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for(int i = 0;i < n + 1;i++)
            ans[i] = get_num_by_bit1(i);
        return ans;
    }
    private int get_num_by_bit1(int n){
        int cnt = 0;
        for(int i = 0;i < 32;i++)
            cnt += (n>>i) & 1;
        return cnt;
    }

    /**
     * 汉明距离：两个数比特位不同的个数
     * @param x
     * @param y
     * @return 不同比特位个数
     */
    public int hammingDistance(int x, int y) {
        int cnt = 0;
        for(int i = 0;i < 32;i++){
            if(((x >> i) & 1) - ((y>>i) & 1) != 0)
                cnt++;
        }
        return cnt;
    }

    /**
     * 只出现一次的数字
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int cnt = 0;
        for(int x : nums)
            cnt ^= x;
        return cnt;
    }

    /**
     * 获取两个不同数
     * @param nums
     * @return
     */
    public static int[] singleNumber_1(int[] nums) {
        int length = nums.length;
        if(length == 2) return nums;

        int sum = 0;
        for(int x : nums) sum ^= x;

        int ret[] = new int[2];

        int i = 0;
        for(;i < 32;i++){
            if(((sum >> i) & 1) == 1) break;
        }

        for(int j = 0;j < length;j++){
            if(((nums[j] >> i) & 1 ) == 0){
                ret[0] ^= nums[j];
            }
            else{
                ret[1] ^= nums[j];
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        int arr[] = Solution.singleNumber_1(new int[]{1,2,3,4,3,2,1,5});
        for(int x : arr) System.out.print(x + " ");
    }
}